1. Field of the Invention
The field of the invention is that of the encoding of digital data and especially source data organized in blocks of data, or messages, that are independent of one another and have to be encoded and decoded on a unit basis.
More specifically, the invention relates to a method and device of convolutive type error-correcting encoding adapted to the constraints laid down by the transmission of messages and especially short messages (for example of about some tens or some hundreds of bits). The invention also relates to a decoding method and device adapted to the encoding method of the invention.
The invention can be applied in all cases where it is necessary to transmit digital information with a certain degree of reliability. A preferred field of application of the invention is that of digital transmission on highly noise-infested channels. For example, the invention can be implemented for the transmission and reception of signals by satellite. In particular, the invention can be used for communications with orbiting satellites. Indeed, in systems that implement such satellites, communications can only take place in very short data bursts, when the satellites are in the axis of the terrestrial antenna.
The invention can also be advantageously used for space transmissions towards or between space vehicles and/or space probes and in all cases where the reliability of the decoding is of vital importance.
More generally, however, the invention can be applied in the same way to all types of transmission, by RF channels or by cable. In particular, it can be used for digital radiocommunications systems such as the GSM system. Another possible application is that of data transmission on computer networks and especially on the Internet.
Any digital signal, whatever its origin, may be encoded and decoded according to the invention provided that it is organized in blocks of fixed size.
2. Description of the Prior Art
It is known that convolutive encoders are particularly efficient in terms of error correction quality. It will be recalled that, in general, the convolutive codes are codes that associate at least one encoded data element with each source data element to be encoded, this encoded data element being obtained by the modulo 2 summation of this source data element with at least one of the previous source data elements. Thus each encoded symbol is a linear combination of the source data element to be encoded and the previous source data elements taken into account.
In the decoder, the original data elements are most usually reconstructed by means of a maximum likelihood algorithm, for example the Viterbi algorithm, whose decisions may, if necessary, be weighted. This algorithm takes account of a sequence of received encoded symbols to give an estimation of each encoded data element at transmission in determining the source sequence that most probably corresponds to the received sequence.
Among the convolutive codes, there is a very advantageous technique known as the "turbo-code". Turbo-codes are described in particular in the European patent document EP-92 460013.3 entitled "Procede de codage correcteur d'erreurs a au moins deux encodages convolutifs systematiques en parallele, Procede de decodage iteratif, module de decodage et decodeur correspondents" (Method of error correcting-encoding with at least two systematic convolutive encodings in parallel, iterative decoding method and corresponding decoding module and decoder), and in the article by C. Berrou, A. Glavieux and P. Thitimajshima, "Near Shannon limit error-correcting coding and decoding: `turbo-codes`", Proceedings of IEEE ICC '93, Geneva, pp. 1064-1070, May 1993.
Turbo-codes are quasi-optimal binary correcting codes inasmuch as their corrective capacity is close to the theoretical limit predicted by Shannon in 1947.
A turbo-code is built out of a parallel concatenation of recursive systematic convolutive (CSR) codes coupled by a non-uniform interleaving.
The decoding, which cannot be comprehensive given the very large number of states to be considered, makes use of an iterative process relying on the concept of extrinsic information. The decoding complexity is compatible with the present densities of integration on silicon, and this technique is already leading to the creation of physical embodiments.
Turbo-codes and more generally convolutive encoding are quite appropriate to the transmission of long messages, for example with non-stop broadcasting.
By contrast, when it is necessary to protect short messages with a length N, there is a problem of knowing the final state of the encoder after the N bits have been applied to it. If this information is not given, or if the state of the encoder is not set at a known value by the application of additional bits ("tail bits"), the decoder, for example a Viterbi decoder, loses its corrective capacity.
Furthermore, if the code is not "closed", it is impossible to implement a sequential decoding that always relies, in the course of an iterative process, on the same decoding unit.
At another level, and again for short messages, it is difficult to use the technique of concatenation (typically a BCH block code or a Read-Solomon code followed, after interleaving, by a convolutive code) to obtain high correcting capacity: either the block code requires a block length greater than that of the message (in the case of the Read-Solomon code) or else the size of the interleaving is far too great (as in the case of the BCH code). It is therefore the practice today to make do with either a convolutive code with termination bits or a block code, and therefore to accept a very ordinary level of correction capacity.
Studies have been conducted on block turbo-codes using BCH codes as elementary codes. These are described especially in the article by R. Pyndiah, A. Glavieux, A. Picart and S. Jacq, "Near optimum decoding of product codes" in Proceedings of IEEE GLOBECOM '94, Vol. 1/3, pp. 339-343, November-December 1994.
The results are excellent but the encoding pattern has drawbacks such as the complexity of the decoder, a lack of flexibility in encoding efficiency levels and large sizes of blocks. The convolutive block turbo-codes described hereinafter also give excellent performance characteristics. They are relatively simple to decode and provide great flexibility in the choice of encoding efficiency and block sizes.
The goal of the invention in particular is to overcome these different drawbacks of the prior art.